/*
 * @lc app=leetcode.cn id=155 lang=cpp
 *
 *
 */

// @lc code=start

#include <deque>
#include <iostream>  // std::cout
#include <stack>     // std::stack
#include <vector>
using namespace std;
class Solution
{
 public:
  vector<int> maxInWindows(const vector<int> &num, unsigned int size)
  {
    vector<int> result;
    if (size > num.size() || size < 1) return result;

    // 双端队列(存索引，且该索引对应的num[deque.front()]值是递减队列，队首deque.front()为最大)
    // 队列中存的元素中，队首元素为当前窗口下的最大值，
    // 队首外的元素为最大值之后的次大值（队列中索引指向元素为从大到小，均为局部极大值点）
    deque<int> index;

    for (unsigned int i = 0; i < num.size(); i++)
    {
      while (!index.empty() && num[i] >= num[index.back()])
      {
        // 从队尾依次弹出队列中比当前num值小的元素, 同时也能保证队列首元素为当前窗口最大值下标
        index.pop_back();
      }
      //
      index.push_back(i);

      // 如果队首索引所指向的元素已经不在窗口中了就弹出
      if (!index.empty() && i - index.front() + 1 > size) index.pop_front();

      // 当有完整的窗口覆盖后才开始push最大值
      if (i >= size - 1) result.push_back(num[index.front()]);
    }
    return result;
  }
};

int main()
{
  Solution solute;
  vector<int> pushV = {1, 2, 3, 4, 5};
  vector<int> popV = {4, 5, 3, 2, 1};
  int i = solute.IsPopOrder(pushV, popV);
  cout << "i:" << i << endl;
  return 0;
}

// @lc code=end
